package com.graph6;

import java.util.*;

public class TopologicalSort2 {
	/**
	 * <code>
	 * 	LIBRARY          LIBRARY DEPENDENCIES
	=======          ====================
	des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
	dw01             ieee dw01 dware gtech
	dw02             ieee dw02 dware
	dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
	dw04             dw04 ieee dw01 dware gtech
	dw05             dw05 ieee dware
	dw06             dw06 ieee dware
	dw07             ieee dware
	dware            ieee dware
	gtech            ieee gtech
	ramlib           std ieee
	std_cell_lib     ieee std_cell_lib
	synopsys
	 * </code>
	 * 
	 */

	public static void main(String[] args) {
//    	              0   1      2              3     4      5     6    7
		String s = "std, ieee, des_system_lib, dw01, dw02, dw03, dw04, dw05, "
//        		    8     9     10      11    12        13           14
				+ "dw06, dw07, dware, gtech, ramlib, std_cell_lib, synopsys, 15, 16, 17, 18, 19, 20";
		int[][] edges = new int[][] { //
				{ 2, 0 }, { 2, 14 }, { 2, 13 }, { 2, 4 }, { 2, 3 }, { 2, 12 }, { 2, 1 }, //
				{ 3, 1 }, { 3, 10 }, { 3, 11 }, //
				{ 4, 1 }, { 4, 10 }, //
				{ 5, 0 }, { 5, 14 }, { 5, 10 }, { 5, 4 }, { 5, 3 }, { 5, 1 }, { 5, 11 }, //
				{ 6, 1 }, { 6, 3 }, { 6, 10 }, { 6, 11 }, //
				{ 7, 1 }, { 7, 10 }, //
				{ 8, 1 }, { 8, 10 }, //
				{ 9, 1 }, { 9, 10 }, //
				{ 10, 1 }, //
				{ 11, 1 }, //
				{ 12, 0 }, { 12, 1 }, //
				{ 13, 1 },//	
				{ 15, 16 },
				{ 17, 18 },
				{ 19, 20 },
				{ 15, 20 },	
		};
		Graph g = new Graph(s, edges);

		// System.out.println(g.adjacency);
		String[] libs = s.split(",");
		// 输出二维数组坐标图
		// System.out.print("\t");
		for (int j = 0; j < 20; j++) {
			System.out.print(" " + libs[j] + " " + j);
		}
		System.out.println();

		System.out.print("\t");
		for (int j = 0; j < 20; j++) {
			System.out.print("\t" + j);
		}
		System.out.println();

		for (int i = 0; i < g.adjacency.length; i++) {

			System.out.print(i + "\t|\t");
			for (int j = 0; j < g.adjacency[i].length; j++) {
				System.out.print((g.adjacency[i][j] ? 1 : 0) + "\t");
			}
			System.out.println();
		}

		System.out.println("Topologically sorted order: ");
		List<String> sort = g.topoSort();
		System.out.println(sort);
		for (String str : sort) {
			for (int i = 0; i < libs.length; i++) {
				String lib = libs[i];

				if (lib.equals(str)) {
					System.out.print("\t" + str + " " + i);
					break;
				}

			}
		}
		HashMap<Integer, int[][]> map = new HashMap<Integer, int[][]>();

		List<Tx> txs = new ArrayList<Tx>();
		for (int[] edge : edges) {
			txs.add(new Tx(edge[0], edge[1]));
		}
		int group = 0;
		while (!txs.isEmpty()) {// 还有数据
			for (Tx tx : txs) {
				if (hasMap(group, tx, txs, map)) {// 没有依赖的元素移出
					txs.remove(tx);
				}
			}
		}
	}

	private static boolean hasMap(int group, Tx tx, List<Tx> txs, HashMap<Integer, int[][]> map) {

		return false;
	}

}

class Tx22 {
	private int from;

	private int to;

	public int getFrom() {
		return from;
	}

	public void setFrom(int from) {
		this.from = from;
	}

	public int getTo() {
		return to;
	}

	public void setTo(int to) {
		this.to = to;
	}

	public Tx22(int from, int to) {
		this.from = from;
		this.to = to;
	}

	@Override
	public String toString() {
		return "Tx [from=" + from + ", to=" + to + "]";
	}

	@Override
	public int hashCode() {
		return Objects.hash(from, to);
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Tx22 other = (Tx22) obj;
		return from == other.from && to == other.to;
	}

	
}

class Graph22 {
	String[] vertices;
	boolean[][] adjacency;
	int numVertices;

	public Graph22(String s, int[][] edges) {
		vertices = s.split(",");
		numVertices = vertices.length;
		adjacency = new boolean[numVertices][numVertices];

		for (int[] edge : edges)
			adjacency[edge[0]][edge[1]] = true; // 坐标上设置点
	}

	List<String> topoSort() {
		List<String> result = new ArrayList<>();
		List<Integer> todo = new LinkedList<>();

		for (int i = 0; i < numVertices; i++)
			todo.add(i);

		try {
			outer: while (!todo.isEmpty()) {// 还有数据
				for (Integer r : todo) {
					if (!hasDependency(r, todo)) {// 没有依赖的元素移出
						todo.remove(r);
						System.out.println(vertices[r] + " " + r + "\r------------------------\r");
						result.add(vertices[r]);
						// no need to worry about concurrent modification
						continue outer;
					}
				}
				throw new Exception("Graph has cycles");
			}
		} catch (Exception e) {
			System.out.println(e);
			return null;
		}
		return result;
	}
	List<Integer> topoSort2() {
		List<Integer> result = new ArrayList<>();
		List<Integer> todo = new LinkedList<>();

		for (int i = 0; i < numVertices; i++)
			todo.add(i);

		try {
			outer: while (!todo.isEmpty()) {// 还有数据
				for (Integer r : todo) {
					if (!hasDependency(r, todo)) {// 没有依赖的元素移出
						todo.remove(r);
						System.out.println(vertices[r] + " " + r + "\r------------------------\r");
						result.add(r);
						// no need to worry about concurrent modification
						continue outer;
					}
				}
				throw new Exception("Graph has cycles");
			}
		} catch (Exception e) {
			System.out.println(e);
			return null;
		}
		return result;
	}

	List<String> toGroup() {
		List<String> result = new ArrayList<>();
		List<Integer> todo = new LinkedList<>();

		for (int i = 0; i < numVertices; i++)
			todo.add(i);

		try {
			outer: while (!todo.isEmpty()) {// 还有数据
				for (Integer r : todo) {
					if (!hasDependency(r, todo)) {// 没有依赖的元素移出
						todo.remove(r);
						System.out.println(vertices[r] + " " + r + "\r------------------------\r");
						result.add(vertices[r]);
						// no need to worry about concurrent modification
						continue outer;
					}
				}
				throw new Exception("Graph has cycles");
			}
		} catch (Exception e) {
			System.out.println(e);
			return null;
		}
		return result;
	}

	boolean hasDependency(Integer r, List<Integer> todo) {
		for (Integer c : todo) {
			if (adjacency[r][c]) {
				System.out.println("\t" + r + " --> " + c);
				return true;
			}
		}
		return false;
	}
}